package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202408;

import java.util.HashMap;
import java.util.Map;

public class leetcode20240825 {
    // 记忆化回溯
    private Map<Integer,Boolean> memo=new HashMap<>();
    public boolean canPartitionKSubsets(int[] nums,int k){
        int sum=0;
        for(int i=0;i<nums.length;i++) sum+=nums[i];
        if(sum%k!=0) return false;
        int target=sum/k;
        int used=0;
        int[] bucket=new int[k+1];
        return backtrack(nums,0,bucket,target,k,used);
    }

    private boolean backtrack(int[] nums,int start,int[] bucket,int target,int k,int used){
        if(k==0) return true;

        if(bucket[k]==target){
            boolean res=backtrack(nums,0,bucket,target,k-1,used);
            memo.put(used,res);
            return res;
        }

        if(memo.containsKey(used)){
            return memo.get(used);
        }

        for(int i=start;i<nums.length;i++){
            if(((used>>i) & 1)==1) continue;
            if(bucket[k]+nums[i]>target) continue;

            bucket[k]+=nums[i];
            used |=1<<i;

            if(backtrack(nums,i+1,bucket,target,k,used)) return true;

            bucket[k]-=nums[i];
            used ^=1<<i;
        }
        return false;
    }

}
